package chapter5;

public class PrimeGenerator {
	
	private static boolean[] crossOut;
	private static int[] result;

	public static int[] generatePrimes(int maxValue){
		if(maxValue < 2){
			return new int[0];
		}else{
			uncrossIntegersUpTo(maxValue);
			crossOutMultiples();
			putUncrossedIntegerIntoResult();
			return result;
		}
	}
	
	private static void uncrossIntegersUpTo(int maxValue){
		crossOut = new boolean[maxValue + 1];
		for (int i = 2; i < crossOut.length; i++) {
			crossOut[i] = false;
		}
	}
	
	private static void crossOutMultiples(){
		int limit = determineIterationLimit();
		
		for (int i = 2; i <= limit; i++) {
			if(!crossOut[i]){
				crossOutMultiplesOf(i);
			}
		}
	}
	
	private static void crossOutMultiplesOf(int i){
		for (int multiple = 2*i; multiple < crossOut.length; multiple += i) {
			crossOut[multiple] = true;
		}
	}
	
	private static int determineIterationLimit(){
		return (int) (Math.sqrt(crossOut.length));
	}
	
	private static void putUncrossedIntegerIntoResult(){
		result = new int[numOfUncrossedIntegers()];
		
		for (int i = 2, j = 0; i < crossOut.length; i++) {
			if(crossOut[i]){
				result[j++] = i;
			}
		}
	}
	
	private static int numOfUncrossedIntegers(){
		int count = 0;
		for (int i = 2; i < crossOut.length; i++) {
			if(!crossOut[i]){
				count++;
			}
		}
		return count;
	}
	
	// 最初待重构版本（为了重现重构过程，暂且保留此代码）
	public static int[] PrimeGenerator(int maxValue){
		if(maxValue >= 2){
			int s = maxValue + 1;
			Boolean[] f = new Boolean[s];
			int i;
			
			for(i = 0; i < s; i++){
				f[i] = true;
			}
		
			f[0] = f[1] = false;
			
			int j;
			for (i = 2; i < Math.sqrt(s) + 1; i++) {
				for(j = 2 * i; j < s; j++){
					f[j] = false;
				}
			}
			
			int count = 0;
			for(i = 0; i < s; i++){
				if(f[i]){
					count++;
				}
			}
			
			int[] primes = new int[count];
			for(i =0 ,j =0; i < s; i++){
				if(f[i]){
					primes[j++] = i;
				}
			}
			return primes;
		}else{
			return new int[0];
		}
	}

}
